package tree;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

/**
 * Node{data,weight,left,right}
 * 得到一个字符串"i like like like java do you like a java"对应的byte[]数组
 * 编写一个方法，将准备构件赫夫曼树的Node 节点放到 List ,形式Node[date=97,weight=5],Node[]....
 * 可以通过list创建对应的赫夫曼树.
 */
public class HuffmanTree {
    public static void main(String[] args) {
        int arr[] = {13, 7, 8, 3, 29, 1};
        Node1 huffmanTree = createHuffmanTree(arr);
        System.out.println("遍历");
        preOrder(huffmanTree);


    }

    public static Node1 createHuffmanTree(int[] arr) {
        ArrayList<Node1> node1s = new ArrayList<>();
        for (int v : arr) {
            node1s.add(new Node1(v));
        }
        while (node1s.size() > 1) {
            Collections.sort(node1s);
            System.out.println("nodes=" + node1s);
            Node1 leftNode = node1s.get(0);
            Node1 rightNode = node1s.get(1);
            Node1 parent = new Node1(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            //从ArrayList删除处理过的二叉树
            node1s.remove(leftNode);
            node1s.remove(rightNode);
            //将parent加入到nodes
            node1s.add(parent);
        }
        return node1s.get(0);
    }

    public static void preOrder(Node1 root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("是空树");
        }
    }
}

class Node1 implements Comparable<Node1> {
    int value;
    Node1 left;
    char c;

    public char getC() {
        return c;
    }

    public void setC(char c) {
        this.c = c;
    }

    Node1 right;
    //前序

    public Node1(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node1{" +
                "value=" + value +
                '}';
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(Node1 o) {
        return this.value - o.value;
    }
}
/**
 *
 */

